#include <stdio.h>
#include <stdlib.h>

#include <unistd.h>

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/msg.h>
#include <string.h>

#include <math.h>

#include <time.h>


typedef struct msgbuf {
	long mtype;
	int pi;
} message_buf;


void libera_matriz (int m, int n, int **v){
    int  i;
    for (i=0; i<m; i++) free (v[i]);
    free (v);
}


int **aloca_matriz(int m, int n) {
	int **v; 
	int i;    
	if (m < 1 || n < 1) { 
		printf("Erro: Parametro invalido");
		return NULL;
	}

	v = (int **) malloc (m * sizeof(int *));
	if (v == NULL) {
		printf("Erro: Memoria Insuficiente");
		return NULL;
	}

	for (i = 0; i < m; i++) {
		v[i] = (int*) malloc (n * sizeof(int));
		if (v[i] == NULL) {
			printf("Erro: Memoria Insuficiente");
			return NULL;
		}
	}
	return v; 
}

int *aloca_vetor(int m) {
	int *v; 

	if (m < 1) { 
		printf("Erro: Parametro invalido");
		return NULL;
	}

	v = (int*) malloc (m * sizeof(int));
	if (v == NULL) {
		printf("Erro: Memoria Insuficiente");
		return NULL;
	}

	return v;
}

int main(void) {
	int m, k;
	int i, j;
	int **v;
	int *pi;
	
	int maior, menor, maior_i, maior_j, menor_i, menor_j;
	int maior_pi, maior_pi_i, menor_pi,menor_pi_i;
	int desvio_padrao, media;
	int meio_intervalo;

    int msqid;
    int msgflg = IPC_CREAT | 0666;

    key_t key;
	message_buf sbuf, rbuf;
    size_t buf_length;
	
	// Criando canal de comunicação
	key = 1234;
	if ((msqid = msgget(key, msgflg )) < 0) {
		perror("msgget");
		exit(1);
	}

	// Inicializando o random
	srand(time(NULL));

	while(1) {
		printf("\nEntre com as dimensões da matriz: ");
		scanf ("%d %d", &m, &k);
		
		if ((m == 0 && k == 0) || (m != k)) break;
		
		// Guardando o tempo de iníicio
		double ini = time(0); 		
		
		v = aloca_matriz(m, k);
		pi = aloca_vetor(m);

		// Gerando matriz aleatoria -100 a +100
		for(i = 0; i < m; i++) {
			for(j = 0; j < k; j++) {
				v[i][j] = (rand() % 201) - 100; 
			}
			pi[i] = 0;
		}

		menor = v[0][0];
		maior = v[0][0];
		maior_i = 0;
		maior_j = 0;
		menor_i = 0;
		menor_j = 0;
		
		// Calculando o maior e o menor
		for(i = 0; i < m; i++) {
			for(j = 0; j < k; j++) {
				if (v[i][j] > maior) {
					maior = v[i][j];
					maior_i = i;
					maior_j = j;
				}
				if (v[i][j] < menor) {
					menor = v[i][j];
					menor_i = i;
					menor_j = j;
				}
			}
		}
		buf_length = sizeof(sbuf);

		meio_intervalo = m/2;

		// Inicializando os subprocessos
		if(fork() == 0) {
			// Processo filho
			for(i = 0; i < meio_intervalo; i++) {

				sbuf.pi = 0;
				// Calculando produto interno
				for(j = 0; j < k; j++) {
					sbuf.pi += v[i][j] * v[j][i]; 
				}	

				// Criando mensagem
				sbuf.mtype = i + 1;
       			buf_length = sizeof(sbuf);

				// Enviando mensagem
				if (msgsnd(msqid, &sbuf, buf_length, 0) < 0) {
					perror("msgsnd");
					exit(1);
				} 
        	}
			exit(0);
		} else {
			if(fork() == 0) {
				// Processo filho
				for(i = meio_intervalo; i<m; i++) {

					sbuf.pi = 0;
					// Calculando produto interno
					for(j = 0; j < k; j++) {
						sbuf.pi += v[i][j] * v[j][i]; 
					}	

					// Criando mensagem
					sbuf.mtype = i + 1;
					buf_length = sizeof(sbuf);

					// Enviando mensagem
					if (msgsnd(msqid, &sbuf, buf_length, 0) < 0) {
						perror("msgsnd");
						exit(1);
					} 
				}
				exit(0);
			}
		}

		media = 0;

		// Recebendo mensagem
		for(i = 0; i < m; i++) {
			if (msgrcv(msqid, &rbuf, buf_length, i + 1, 0) < 0) {
				perror("msgrcv");
				exit(1);
			}
			pi[i] = rbuf.pi; 
			media += pi[i];
		}

		media /= m; 
		
		menor_pi = pi[0];
		maior_pi = pi[0];
		maior_pi_i = 0;
		menor_pi_i = 0;
		desvio_padrao = 0;

		// Calculando o maior e o menor pi
		for(i = 0; i < m; i++) {
			desvio_padrao += pow((pi[i] - media), 2); 
			if (pi[i] > maior_pi) {
				maior_pi = pi[i];
				maior_pi_i = i;
			}
			if (pi[i] < menor_pi) {
				menor_pi = pi[i];
				menor_pi_i = i;
			}
		}	

		// Calculando o desvio padrão
		desvio_padrao = sqrt(desvio_padrao / (m-1));


		// Imprimindo os resultados
		/*
		printf("\n--------------------\n");
		printf("matriz\n");
		
		for(i = 0; i < m; i++) {
			for(j = 0; j < k; j++) {
				printf("%d ", v[i][j]); 
			}
			printf("\n");
		} 

		printf("\n--------------------\n");
		
		printf("Maior: %d em (%d, %d)\n", maior, maior_i, maior_j);
		printf("Menor: %d em (%d, %d)\n", menor, menor_i, menor_j);
		
		printf("\n--------------------\n");
		
		printf("vetor produto interno\n");
		for(i = 0; i < m; i++) {
			printf("%d ", pi[i]); 
		}
		printf("\n");
		
		printf("\n--------------------\n");	
		printf("Maior PI: %d em (%d)\n", maior_pi, maior_pi_i);
		printf("Menor PI: %d em (%d)\n", menor_pi, menor_pi_i);
		printf("Desvio Padrão: %d \n", desvio_padrao);
		*/
	
	 	printf("\n--------------------\n");
	    printf("Utilizando algoritmo paralelo com m = k = %d\n", m);

		libera_matriz(m, k, v);
		free(pi);
		
		printf("\n--------------------\n");
		printf("Tempo de Execucao: %f segundos\n", time(0) - ini);
 	}

	// Fechando canal de comunicação
	close(msqid);

	return 0;
}

